// thread.h 
//	Data structures for managing threads.  A thread represents
//	sequential execution of code within a program.
//	So the state of a thread includes the program counter,
//	the processor registers, and the execution stack.
//	
// 	Note that because we allocate a fixed size stack for each
//	thread, it is possible to overflow the stack -- for instance,
//	by recursing to too deep a level.  The most common reason
//	for this occuring is allocating large data structures
//	on the stack.  For instance, this will cause problems:
//
//		void foo() { int buf[1000]; ...}
//
//	Instead, you should allocate all data structures dynamically:
//
//		void foo() { int *buf = new int[1000]; ...}
//
//
// 	Bad things happen if you overflow the stack, and in the worst 
//	case, the problem may not be caught explicitly.  Instead,
//	the only symptom may be bizarre segmentation faults.  (Of course,
//	other problems can cause seg faults, so that isn't a sure sign
//	that your thread stacks are too small.)
//	
//	One thing to try if you find yourself with seg faults is to
//	increase the size of thread stack -- ThreadStackSize.
//
//  	In this interface, forking a thread takes two steps.
//	We must first allocate a data structure for it: "t = new Thread".
//	Only then can we do the fork: "t->fork(f, arg)".
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#ifndef THREAD_H
#define THREAD_H

#include "copyright.h"
#include "utility.h"
#include "list.h"

#ifdef USER_PROGRAM
#include "machine.h"
#include "addrspace.h"
#endif

// CPU register state to be saved on context switch.  
// The SPARC and MIPS only need 10 registers, but the Snake needs 18.
// For simplicity, this is just the max over all architectures.
#define MachineStateSize 18 


// Size of the thread's private execution stack.
// WATCH OUT IF THIS ISN'T BIG ENOUGH!!!!!
#define StackSize	(4 * 1024)	// in words


// Thread state
enum ThreadStatus { JUST_CREATED, RUNNING, READY, BLOCKED };

// external function, dummy routine whose sole job is to call Thread::Print
extern void ThreadPrint(int arg);	 


// List to be used for child processes because, you know, the actual 
// list class included in nachos is not a list and we're tired of playing
// with it.

class OpenFile;
class Thread; // dummy call for construction of list of threads
/*
template<typename T>
struct nodeType
{
	T info;
	int tag; // unique num for the data in the list
	nodeType<T> *next;
};

template <typename T>
class linkedList
{
public:

	//function to see if list contains elements
	bool linkedList<typename T>::isEmpty()
	{
		return(first==NULL);
	}

	//return the number of elements
	linkedList<typename T>::Length()
	{
		return count;
	}
	
	//return the first item 
	T linkedList<typename T>::firstItem()
	{
		if(!isEmpty())
		{
			return first->info;			
		}
		else
		{
			return NULL;
		}
	}
	
	//return the last item
	T linkedList<typename T>::lastItem()
	{
		if(!isEmpty())
		{
			return last->info;			
		}
		else
		{
			return NULL;
		}
	}
	

	//function to append an item to the list
	void linkedList<typename T>::appendItem(const T& newItem, int newTag)
	{
		if(newItem == NULL || newTag == NULL){
			printf("CANT ADD NULL TO LIST\n");
		}

		nodeType<T> newNode;
		newNode->info=newItem;
		
		if(first == NULL){
			first->next = first;
			first->tag = newTag;
			first = newNode;
		}
		else{
			last->next = last;
			last->tag = newTag;
			last = newNode;
		}
		count++;
	}
	
	// finds an item in the list
	T linkedList<typename T>::findItem(int newTag){
		
		nodeType<T> temp;
		temp = first;
		
		while(temp != NULL){
			if(temp->tag == newTag){
				return temp;
			}
			temp = temp->next;
		}
		
		return NULL;
	}
	
	//constructor	
	linkedList<typename T>::linkedList()
	{
		first=NULL;
		last=NULL;
		count=0;
	}

	//destructor	
//	template<class T>
	linkedList<typename T>::~linkedList()
	{
		nodeType *temp;

		while(first!=NULL)
		{
			temp=first;
			first=first->next;
			delete temp;
		}
		last=NULL;
		count=0;
	}

protected:
	nodeType *first;	//pointer to first node
	nodeType *last;	//pointer to last node
	int count;	//stores number of items in the list
}; */

typedef struct nodeType{
	nodeType(OpenFile* Opened, int FileID){
		file = Opened; 
		tag = FileID;
		this->next = NULL;
	}
	OpenFile* file;
	int tag;
	nodeType* next;
};

// a list of unique child nodes of a parent thread
// identified by a key
//	defined and implemented the good old fashioned C++ way (all at once)
class openedList{
	private:
		nodeType* first;
		int size;

	public:
		openedList(){
			first = NULL;
			size = 0;
		}		
		
		// secondary constructor that allows for adding first child
		openedList(OpenFile* newFile, int ID){
			size = 0;
			addFile(newFile, ID);
		}
		
		// deallocate all remaining nodes in the list
		~openedList(){
		//	printf("In Destructor\n");
			// remove all children in the list deallocating memory
			while(!isEmpty())
				removeFile(getFirst()->tag);
		
		}
		
		// add a new node and increment size
		void addFile(OpenFile* newFile, int ID){
		
			bool didFind = false;
		//	printf("Adding child %d to list.\n", ID);
			
			//if the list is empty create new node for the first child
			if(isEmpty()){
		//		printf("IS empty is true \n");
				first = new nodeType(newFile, ID);
		//		printf("File %d has been added as first element of list.\n", ID);
				size++;
		//		printf("Size is %d \n", size);
				return;
			}else{
				// iterate through the list and if babyName is not unique
				//	notify user and exit, otherwise add it to the end of the list
				
				nodeType* temp = first;			
				for(temp; temp != NULL; temp = temp->next){
					// ensure unique files and keys
					if(temp->file == newFile || temp->tag == ID){
						didFind = true;					
					}				
				}
				
				// add child to the end of the list
				temp = new nodeType(newFile, ID);
				size++;
			}
			
		}
		
		// remove a child from the list of children and decrement list size
		void removeFile(int rmFile){	
			
			printf("\nAttempting to remove file %d.\n", rmFile);
			// if nothing in the list stop wasting time and get out
		
			if(isEmpty()){
		//		printf("Size is %d \n", size);
		//		printf("List is empty, can't remove file %d.\n", rmFile);
				return;
			}
			
			// if the first element of the list is the target
			//	take 'em out and deallocate memory of old first
			if(first->tag == rmFile){
			//	printf("Removing child %d. \n", first->tag);
				nodeType* temp = first;
				first = first->next;
				delete temp;
				size--;
			
			}else{		// otherwise
				nodeType* temp = first;
				nodeType* gtfo = NULL;
				
				// iterate through the list 
				for(temp; temp != NULL ; temp = temp->next){
					// if find the file in the list 
					//	mark the file for deletion and exit loop
					if(temp->tag == rmFile){
						gtfo = temp;
						break;
					}					
				}
				
				// if file is found notify of removal and deallocate the node
				if(gtfo != NULL){
			//		printf("Removing file %d. \n", gtfo->tag);
					temp = temp->next;
					delete gtfo;
					size--;
										
				}else{
					printf("Unable to find file %d in open file list, NOT REMOVING.\n",rmFile);
				}				
			}	
				
		}
		// return a pointer to the first node in the list
		nodeType* getFirst(){
			return first;
		}
		
		
		bool isEmpty(){
			if(size == 0){
				return true;
			}
			else return false;
		}
		
		// return the size of the list
		int getSize(){return size;}
		
		// return if list contains the passed child key
		OpenFile* find(int id){
			for(nodeType* temp = getFirst(); temp != NULL; temp = temp->next){
				if(temp->tag == id)
					return temp->file;
			}
			return NULL;
		}
		
		OpenFile* findByFile(OpenFile* myF){
			for(nodeType* temp = getFirst(); temp != NULL; temp = temp->next){
				if(temp->file == myF)
					return temp->file;
			}
			return NULL;
		}
};

typedef struct node{
	node(Thread* newBirth, int babyName){
		childThread = newBirth; 
		key = babyName;
		this->next = NULL;
	}
	Thread* childThread;
	int key;
	node* next;
};

// a list of unique child nodes of a parent thread
// identified by a key
//	defined and implemented the good old fashioned C++ way (all at once)
class childList{
	public:
		childList(){
			first = NULL;
			size = 0;
		}		
		
		// secondary constructor that allows for adding first child
		childList(Thread* newBirth, int babyName){
			size = 0;
			addChild(newBirth, babyName);
		}
		
		// deallocate all remaining nodes in the list
		~childList(){
			// remove all children in the list deallocating memory
			while(!isEmpty())
				removeChild(getFirst()->key);
		
		}
		
		// add a new node and increment size
		void addChild(Thread* newBirth, int babyName){
		
		//	printf("Adding child %d to list.\n", babyName);
			
			//if the list is empty create new node for the first child
			if(isEmpty()){
				first = new node(newBirth, babyName);
			//	printf("Child %d has been added as first element of list.\n", babyName);
				size++;
				return;
			}else{
			
				// iterate through the list and if babyName is not unique
				//	notify user and exit, otherwise add it to the end of the list
				node* temp = first;
				
				for(temp; temp != NULL; temp = temp->next){
					// ensure unique keys
					if(temp->key == babyName){
						printf("Key is not unique, not readding child %d.\n", babyName);
						return;						
					}				
				}
				
				// add child to the end of the list
				temp = new node(newBirth, babyName);
			//	printf("Child %d has been added as last element of list.\n", babyName);
				size++;
			}
			
		}
		
		// remove a child from the list of children and decrement list size
		void removeChild(int byeByeBaby){	
			
		//	printf("\nAttempting to remove child %d.\n", byeByeBaby);
			// if nothing in the list stop wasting time and get out
		
			if(isEmpty()){
				printf("List is empty, can't remove child %d.\n", byeByeBaby);
				return;
			}
			
			// if the first element of the list is the target
			//	take 'em out and deallocate memory of old first
			if(first->key == byeByeBaby){
			//	printf("Removing child %d. \n", first->key);
				node* temp = first;
				first = first->next;
				delete temp;
				size--;
			
			}else{		// otherwise
				node* temp = first;
				node* gtfo = NULL;
				
				// iterate through the list 
				for(temp; temp != NULL ; temp = temp->next){
					
					// if find the child in the list 
					//	mark the child for deletion and exit loop
					if(temp->key == byeByeBaby){
						gtfo = temp;
						break;
					}					
				}
				
				// if child is found notify of removal and deallocate the node
				if(gtfo != NULL){
			//		printf("Removing child %d. \n", gtfo->key);
					temp = temp->next;
					delete gtfo;
					size--;
										
				}else{
					printf("Unable to find child %d in child list, NOT REMOVING.\n",byeByeBaby);
				}				
			}	
				
		}
		// return a pointer to the first node in the list
		node* getFirst(){
			return first;
		}
		
		
		// return if the list is empty
		bool isEmpty(){
			if(size == 0){
				return true;
			}
			else return false;
		}
		
		// return the size of the list
		int getSize(){return size;}
		
		// return if list contains the passed child key
		bool contains(int id){
			for(node* temp = getFirst(); temp != NULL; temp = temp->next){
				if(temp->key == id)
					return true;
			}
			return false;
		}
		
	private:
		node* first;
		int size;
};

// The following class defines a "thread control block" -- which
// represents a single thread of execution.
//
//  Every thread has:
//     an execution stack for activation records ("stackTop" and "stack")
//     space to save CPU registers while not running ("machineState")
//     a "status" (running/ready/blocked)
//    
//  Some threads also belong to a user address space; threads
//  that only run in the kernel have a NULL address space.

class Thread {
  private:
    // NOTE: DO NOT CHANGE the order of these first two members.
    // THEY MUST be in this position for SWITCH to work.
    int* stackTop;			 // the current stack pointer
    int machineState[MachineStateSize];  // all registers except for stackTop

  public:
    Thread(char* debugName);		// initialize a Thread 
    ~Thread(); 				// deallocate a Thread
					// NOTE -- thread being deleted
					// must not be running when delete 
					// is called

    // basic thread operations

	void setParent(Thread*);
	Thread* getParent();
	
    void Fork(VoidFunctionPtr func, int arg); 	// Make thread run (*func)(arg)
    void Yield();  				// Relinquish the CPU if any 
						// other thread is runnable
    void Sleep();  				// Put the thread to sleep and 
						// relinquish the processor
    void Finish();  				// The thread is done executing
    
    void CheckOverflow();   			// Check if thread has 
						// overflowed its stack
    void setStatus(ThreadStatus st) { status = st; }
	
	void setID(int i);
	int getID();
	
    char* getName() { return (name); }
    void Print() { printf("%s, ", name); }
	
	void addChild(Thread*);		// add a thread to thread's list of child threads
	void removeChild(Thread*);	// remove thread from list of child threads

	void addExec(OpenFile*);
	void removeExec();
	
	List *Children;
	ListElement *firstChild;
	childList *children;
	

  private:
    // some of the private data for this class is listed above
    int ID;
    int* stack; 	 		// Bottom of the stack 
					// NULL if this is the main thread
					// (If NULL, don't deallocate stack)
    ThreadStatus status;		// ready, running or blocked
    char* name;
	Thread* parentThread;
	OpenFile *exec;
	
    void StackAllocate(VoidFunctionPtr func, int arg);
    					// Allocate a stack for thread.
					// Used internally by Fork()
					
#ifdef USER_PROGRAM
// A thread running a user program actually has *two* sets of CPU registers -- 
// one for its state while executing user code, one for its state 
// while executing kernel code.

    int userRegisters[NumTotalRegs];	// user-level CPU register state

  public:
    void SaveUserState();		// save user-level register state
    void RestoreUserState();		// restore user-level register state

    AddrSpace *space;			// User code this thread is running.
	
	
#endif
};

// Magical machine-dependent routines, defined in switch.s

extern "C" {
// First frame on thread execution stack; 
//   	enable interrupts
//	call "func"
//	(when func returns, if ever) call ThreadFinish()
void ThreadRoot();

// Stop running oldThread and start running newThread
void SWITCH(Thread *oldThread, Thread *newThread);
}

#endif // THREAD_H
